package LeetCode.month02.day54;

import java.util.*;

public class No2197 {
    public List<Integer> replaceNonCoprimes(int[] nums) {
        List<Integer> list = new ArrayList<>();
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            stack.add(nums[i]);
            while(stack.size()>=2){
                int curr = stack.removeLast();
                int pre = stack.removeLast();
                if(GCD(curr,pre)>1){
                    stack.add(LCM(curr,pre));
                }else{
                    stack.add(pre);
                    stack.add(curr);
                    break;
                }
            }
        }
        int n = stack.size();
        for (int i = 0; i < n; i++) {
            list.add(stack.removeFirst());
        }
        return list;
    }

    public int GCD(int x,int y){        //最大公因数  3/4  3、6  6 4
        if(x==0){
            return y;
        }
        while(y!=0){
            int temp =y;
            y = x%y;
            x = temp;
        }
        return x;
    }

    public int LCM(int x,int y){        //最小公倍数
        int a = GCD(x,y);
        return (x/a)*y;
    }
}
